package 力扣.字符串.字典树;

import java.util.*;

/**
 * @Description TODO
 * @Author ChanAn
 * @Date 2021/10/9 18:41
 **/
public class 字典序排数386 {
    /**
     * 给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
     *
     * 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法
     *
     * 示例 1：
     *
     * 输入：n = 13
     * 输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
     * 示例 2：
     *
     * 输入：n = 2
     * 输出：[1,2]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/lexicographical-numbers
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */


    public List<Integer> lexicalOrder(int n) {
        ArrayList<Integer>  lexicalList = new ArrayList<>();
        for (int i = 1; i <= n && i <= 9; i++) {
            int t = i;
            lexicalList.add(t);
            //递归
            ditionaryTree(t , n ,lexicalList);
        }
        return lexicalList;
    }

    private void ditionaryTree(int t, int  n ,ArrayList<Integer> lexicalList) {
        t *= 10;
        for (int i = 0; ((t + i) <= n && i <= 9); i++) {
            int te = t + i;
            lexicalList.add(te);
            ditionaryTree(te, n, lexicalList);
        }

    }

    public static void main(String[] args) {
        字典序排数386 thisObject = new 字典序排数386();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> integers = thisObject.lexicalOrder(n);
        System.out.println(integers);
    }
}
